/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package libs.game.sokoban;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import libs.game.Coordinates;
import libs.game.Deadlock;

/**
 *              This class represents simple deadlock in sokoban.
 * @author papi
 */
public class SokobanSimpleDeadlock implements Deadlock {

    private boolean locked;

    
    public SokobanSimpleDeadlock (SokobanGamePlan gamePlan) {
        Map<Coordinates, Path> boxPaths = new HashMap<Coordinates, Path>();
        for (Coordinates box : gamePlan.getBoxes()) {
            boxPaths.put(box, new BoxPath(gamePlan, box));
        }
        Map<Coordinates, Path> goalPaths = new HashMap<Coordinates, Path>();
        for (Coordinates goal : gamePlan.getGoals()) {
            goalPaths.put(goal, new GoalPath(gamePlan, goal, boxPaths));
        }
        compute(gamePlan, goalPaths);
    }

    public SokobanSimpleDeadlock(SokobanGamePlan gamePlan, Map<Coordinates, Path> goalPaths) {
        compute(gamePlan, goalPaths);
    }

    public void compute(SokobanGamePlan gamePlan, Map<Coordinates, Path> goalPaths) {

        locked = false;
        
        // I need this queue to remember where the boxes are.
        PriorityQueue<Set<Integer>> boxesInAreas = new PriorityQueue<Set<Integer>>(goalPaths.values().size(), new Comparator<Set<Integer>>() {
            @Override
            public int compare(Set<Integer> first, Set<Integer> second) {
                return first.size() - second.size();
            }
        });

        // I count goal areas where the each box is.
        int[] boxes = new int[gamePlan.getBoxes().size()];
        for (int i = 0; i < boxes.length; i++) {
            boxes[i] = 0;
        }

        for (Coordinates goal : gamePlan.getGoals()) {
            Set<Integer> goalBoxes = new HashSet<Integer>();
            int boxNum = 0;
            for (Coordinates box : gamePlan.getBoxes()) {
                if (goalPaths.get(goal).get(box) != null) {
                    goalBoxes.add(boxNum);
                    boxes[boxNum]++;
                }
                boxNum++;
            }
            boxesInAreas.add(goalBoxes);
        }

        Set<Integer> minimal = null;
        while ((minimal = boxesInAreas.poll()) != null) {
            if (minimal.size() == 0) {
                locked = true;
                break;
            }
            int minBox = -1;
            for (Integer boxNum : minimal) {
                if (minBox == -1 || boxes[boxNum] < boxes[minBox]) {
                    minBox = boxNum;
                }
            }
            List<Set<Integer>> changed = new ArrayList<Set<Integer>>();
            for (Set<Integer> goalArea : boxesInAreas) {
                if (goalArea.remove(minBox)) {
                    changed.add(goalArea);
                }
            }
            boxesInAreas.removeAll(changed);
            boxesInAreas.addAll(changed);
        }
    }

    @Override
    public boolean isLocked() {
        return locked;
    }

}
